#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct
{
    ElemType *data;
    int size;
}Stable;

void init_stable(Stable &st,int length)
{
    st.size=length;
    st.data=(ElemType*)malloc(sizeof(ElemType)*length);
    //往数组中填入随机数
    srand(time(NULL));
    for(int i=0; i<length; i++)
    {
        st.data[i]=rand()%100;  //生成0~99的随机数
    }
}

//打印数组
void print_stable(Stable st)
{
    for(int i=0; i< st.size ; i++)
    {
        printf("%3d",st.data[i]);
    }
    printf("\n");
}

//快速排序（挖坑法）
void quick_sort(int *data,int left,int right)
{
    if(left >= right)  //递归结束条件
        return;
    int key=data[left];  //确定基准值
    int head=left,tail=right;  //head往后移动找大，tail往后移动赵小
    while(head < tail)
    {
        while(head < tail && data[tail] >= key) //找到小于key值时停下
        {
            --tail;
        }
        data[head]=data[tail];
        while(head < tail && data[head] <= key) //找到大于key值时停下
        {
            head++;
        }
        data[tail]=data[head];
    }
    //将基准值归为
    data[head]=key;
    //此时区间为[left,head-1] head [head+1,right];
    quick_sort(data,left,head-1);
    quick_sort(data,head+1,right);
}

int main() {

    Stable st;
    init_stable(st,15);
    print_stable(st);
    quick_sort(st.data,0,st.size-1);
    print_stable(st);
    return 0;
}

